<!DOCTYPE html>
<html lang="zh-cn">
  <head>
    <meta charset="UTF-8">
    <title>Sucha's Blog - Archive for August, 2020</title>
    <meta name="generator" content="MarkdownProjectCompositor.lua">
    <meta name="author" content="Sucha">
    <meta name="keywords" content="suchang, programming, Linux, Lua">
    <meta name="description" content="Sucha's blog">
    <link rel="shortcut icon" href="../images/ico.png">
    <link rel="stylesheet" type="text/css" href="../styles/blog.css">
    <link rel="stylesheet" type="text/css" href="../styles/prism.min.css">
    <style id="site_theme"></style>
  </head>
  <body>
    <div id="body">
      <div id="text">
	   <!-- Page published by cmark-gfm begins here --><h1>Sucha's Blog ~ Archive for August, 2020</h1>
<p><a id="p1"></a></p>
<div class="date">20年8月17日 周一 23:32</div>
<h2>LuaJIT 下的双链表及 AVL 树</h2>
<p>Lua 描述结构数据方面，只有一种内建结构，就是 table，table 既是 array，又是 hashmap，算是简洁高效的实现，但我们需要一种动态表示元素先后、大小关系的数据结构时，内建的 table 就不合适了，比如常见的 <a href="https://github.com/daurnimator/fifo.lua">fifo</a> 及 <a href="https://github.com/Tieske/binaryheap.lua">binaryheap</a>。</p>
<p>先说优点，上面两个都是使用 table 来描述先后顺序、大小关系的，缺点是，当有插入、删除发生时，时间效率太慢了。其中 fifo 是使用 table 的 array 实现的，需要在删除元素后，对其他的元素做拷贝迁移，避免空位；而 bianryheap，也是使用使用 table 的 array，当元素位置变动时，采用了冒泡算法，对元素重新排位。</p>
<p>空间效率是保住了，但就时间效率来说，太不专业了，O(N^2) 的实现，数据量稍微多一点点，时间不能看。</p>
<p>其实 fifo 算是一种双链表，只是插入是在头尾，算是双链表的特例。双链表下，非头尾的删除发生，时间效率是 O(1) 级别的。其实可以用 table 来描述链表关系，缺点是空间消耗大，为了描述两个相邻元素间的先后顺序，就得用一个 table 实例来做。</p>
<p>我用 Lua 内建的 table 实做了一把，时间效率是很高效的，空间的话，插入 number，10,000,000 级别的插入，内存大概 6G。</p>
<pre><code class="language-source">-- performance
push 1000,000, cost 0.393088
pop  1000,000, cost 0.092984
</code></pre>
<p>在 C 的双链表实现中，需要将链表节点跟数据结构绑定起来，要么是以链表节点为主，链表节点指向数据结构，或者像 Linux Kernel 里面规范化的双链表实现，链表节点实例，放在数据结构中，通过偏移定位数据起点。</p>
<p>但是在 Lua 里面做不到这样，不得不使用 value（值）到 node（节点），以及 node 到 value 的两个 table 来做关系映射，再加上相邻两个 value 的顺序关系使用一个 node（table）来实现，也是空间消耗大的原因。</p>
<h3>LuaJIT 下 cdata 的妙用</h3>
<p>LuaJIT 因为有 FFI，可以创建结构化的 cdata 来描述相邻 node 之间的关系，而不需要使用内建的 table，使得可以花费更少的空间代价，比如下面这样来描述双链表的节点关系：</p>
<pre><code class="language-lua">ffi.cdef [[
struct _cnode {
    struct _cnode *prev;
    struct _cnode *next;
    float key;
};
struct _chead {
    struct _cnode *head;
    struct _cnode *tail;
};
void* calloc(size_t count, size_t size);
void free(void *ptr);
]]
</code></pre>
<p>特别注明 cdata 是 calloc 出来的，不在 gc 管理范围，因为 C 下面的指针，需要保证指向固定的内存地址。其他跟纯 table 实现的双链表一样，需要两个 table 来维护 value 跟 node之间的映射关系，如上面 struct _cnode 下的 key，其实是用于 node 到 value 的 table 的映射 key，原因下面再说。</p>
<p>同样的 AVL 树也可以使用 cdata 来维护节点间的大小关系：</p>
<pre><code class="language-lua">ffi.cdef [[
struct _avl_node {
    struct _avl_node *left;
    struct _avl_node *right;
    struct _avl_node *parent;
    int height;
    float key;
};
struct _avl_root {
    struct _avl_node *node;
};
void* calloc(size_t count, size_t size);
void free(void *ptr);
]]
</code></pre>
<p>以上使用 cdata 描述元素关系时间效率跟纯 table 时间效率一样，空间效率的话，第一个例子下，内存占用不到 4G，地址 <a href="https://github.com/lalawue/list.lua">ffi_list.lua</a> 及 <a href="https://github.com/lalawue/ffi_avl.lua">ffi_avl.lua</a>。</p>
<h3>一些问题</h3>
<p>LuaJIT 下使用 cdata 描述节点关系，遇到了一些问题：</p>
<ul>
<li>cdata 做 key 不稳定，string.format(&quot;%p&quot;) 打印出来看 cdata 的值，经过变量传递后，有变化，做 key 的话，导致 node 到 value 的 mapping 找不到 value，所以 cdata 单独带了一个 float 类型的 key</li>
<li>我设想使用 math.random() 来产生 0 ~ 1 之间的小数做 key，但是在 ffi_list.lua 中，会导致其他的问题，不得不使用了固定小数增长的做法来实现，原因还不清楚，不过我这边自测用的数据范围是 10,000,000 及以上才会出现</li>
</ul>
<p>上面的问题，估计还是要设计一些测试用例来定位一下才好，现在先这样吧。</p>
<h3>后记</h3>
<p>19 号解决了上面遇到的 2 个问题，原因在于 ffi.cdef 使用的 key 宽度是 float，但是 LuaJIT number 的宽度是 double 导致的，我修改 ffi.cdef node 里面的 key 为 double 类型，问题不再出现。</p>
<p>不过我也有疑问，为何 AVL 这边同样的实现，没有暴露出来问题呢。</p>
<p>反正现在修改为多轮循环 test 验证了，验证了几千遍，每次是 1000x1000 次的 push、pop，都是正常的了。</p>
<div class="category"><a href="CategoryProgramming.html">CategoryProgramming</a> / <a href="2020-08.html#p1">Permalink</a> / <a href="https://github.com/lalawue/homepage/discussions/categories/blog" target="_blank">Discussion</a></div>
<p><a id="p0"></a></p>
<div class="date">20年8月02日 周日 20:50</div>
<h2>做了一个 web 框架：cincau</h2>
<p>离职后在家呆了一个月，前面两周在休息，后面两周开始忙起来，想着将手头的数据搭一个可视化的网站出来，可以学习一下 web 前端的库之类的，但是呢，想找一个能 sqlite 和 nginx 的 web framework，找到一个感觉还可以的 <a href="https://github.com/sumory/lor">Lor</a>，但是呢，不支持 sqlite，感觉不算是一个 minimalist 的 web framework，就想着不如自己搭建一个吧。</p>
<p>可是如果搭建，顺便带上自己的 mnet 是肯定的了，当然 nginx 也是要支持的。于是参考了 lor 的不少东西，但更多的其实是自己摸索的，因为时间也比较充足，是先考虑了架构，才开始动手的。</p>
<p>没有浪费之前买的 goodnote 5，用来构思框架了，画了大概 5 个页面，大的模块上，跟 lor 一样，分为基础库，以及具体的项目代码。基础库在 /usr/local/cincau，用来生成基本的 demo 项目，本身包含了所有 proj 用到的的基础库。对上面的简单业务逻辑，封装 engine 层，不区分为 mnet 或者是 nginx，但实际上这两者一定是要区分开的，除非是静态的文件。</p>
<p>基础库里面，细分为 engine 层、router、MVC 逻辑、database、POST 的解析、HTTP Request 这几个部分，其中 MVC 中 view 的 rendering 用了 leafo 的 <a href="https://github.com/leafo/etlua">etlua</a>，这其实是基于 openresty 的 lapis 的一个模版库。database 不出意外，我只考虑了 sqlite3，就是 minimalist 的 web framework，等有需要，在考虑 mysql、postgresql 之类的，毕竟这两者，没有基于 mnet 的接口，只有基于 nginx 的。</p>
<p>在 goodnotes 5 上面花了 3、4 天这样，其实上面这么多细节，都是在完成整个项目后，回头才细化出来的。在草图出来以后，框架搭建花了大概一周，mnet 是基于 ffi_mnet.lua 以及 hyperparser 的回调，拿到 http 数据结构层。而 nginx 是 content_by_lua_file 来驱动的。</p>
<p>然后还继续花了 3、4 天来完善框架细节，比如 POST 以及 HTTP request 的那一套，以及基于这个框架，写了一个 demo project，支持 ment、nginx，包含静态页面、mock 的 model，以及 post x-www-urlencoded 和 multipart/form-data 这几个部分。</p>
<p>该放地址了：<a href="https://github.com/lalawue/cincau">cincau</a>，话说之前也断断续续做过半个 web framework，现在终于点连成了线，水到渠成了。</p>
<p>goodnote 5 画出来的框架图：</p>
<img src="https://tva1.sinaimg.cn/mw690/6f6cc1c0gy1gh9e9xgx85j20h00m00sv.jpg" width=360>
<img src="https://tva1.sinaimg.cn/mw690/6f6cc1c0gy1gh9e9xi8koj20h00m00t3.jpg" width=360>
<img src="https://tva1.sinaimg.cn/mw690/6f6cc1c0gy1gh9e9xq6k9j20h00m03yz.jpg" width=360>
<img src="https://tva1.sinaimg.cn/mw690/6f6cc1c0gy1gh9e9y00d1j20h00m0aam.jpg" width=360>
<img src="https://tva1.sinaimg.cn/mw690/6f6cc1c0gy1gh9e9xlayej20h00m00t2.jpg" width=360>
<img src="https://tva1.sinaimg.cn/mw690/6f6cc1c0gy1gh9e9xzu40j20h00m0t93.jpg" width=360>
<div class="category"><a href="CategoryProgramming.html">CategoryProgramming</a> / <a href="2020-08.html#p0">Permalink</a> / <a href="https://github.com/lalawue/homepage/discussions/categories/blog" target="_blank">Discussion</a></div>
<!-- Page published by cmark-gfm ends here -->
  <div id="foot">2004-<script>var d = new
	Date();document.write(d.getFullYear())</script> &copy;
	Sucha. Powered by MarkdownProjectCompositor.
  </div>
  </div><!-- text -->
  <div id="sidebar">
  </div><!-- sidebar -->
  <script src="../js/prism.min.js" async="async"></script>
  <script src="../js/blog_sidebar.js"></script>
  </div> <!-- body -->
</body>
</html>